
#include "name_hash.h"

namespace qb {
namespace proto{

hash_table::hash_table()
{
    nodes_ = NULL ;
    count_ = 0 ;
    size_ = 0 ;
    //prime_idx_ = -1 ;
}

hash_table::~hash_table()
{
    clear() ;
}

bool hash_table::extend()
{
    /*
        分配新空间
    */
    /*
    int idx = prime_idx_ ;
    if(idx < 0)
        idx = 6 ;
    else
        ++idx ;

    size_t pv = hash_table::get_prime(idx) ;
    if(pv == 0)
        return false ;
    */
    size_t pv = next_size() ;

    size_t len = sizeof(node) * pv ;
    node * nodes = (node *)malloc(len) ;
    if(nodes == NULL)
        return false ;

    memset(nodes , 0 , len) ;

    /*
        拷贝原来的值
    */
    if(nodes_ != NULL)
    {
        for(size_t hidx = 0 ; hidx < size_ ; ++hidx)
        {
            const node& n = nodes_[hidx] ;
            size_t hash = n.code % pv ;
            nodes[hash].code = n.code ;
            nodes[hash].value = n.value ;        
        }

        ::free(nodes_) ;
    }

    //prime_idx_ = idx ;
    size_ = pv ;
    nodes_ = nodes ;

    return true ;
}

bool hash_table::insert(size_t code , size_t value)
{    
    if(nodes_ == NULL)
    {
        //空表
        if(extend() == false)
            return false ;
    }

    size_t hash = code % size_ ;
    while(nodes_[hash].code != 0 && nodes_[hash].code != code)
    {
        //碰撞，使用while循环，避免二次碰撞
        if(extend() == false)
            return false ;

        hash = code % size_ ;       //重算下标
    }

    nodes_[hash].code = code ;
    nodes_[hash].value = value ;
    ++count_ ;

    return true ;
}

bool hash_table::remove(size_t code)
{
    if(nodes_ == NULL)
        return true ;

    size_t hash = code % size_ ;
    if(nodes_[hash].code != code)
        return true ;

    nodes_[hash].code = 0 ;
    nodes_[hash].value = 0 ;
    --count_ ;

    return true ;
}

bool hash_table::update(size_t code , size_t value) 
{
    if(nodes_ == NULL)
        return false ;

    size_t hash = code % size_ ;
    if(nodes_[hash].code != code)
        return false ;

    nodes_[hash].value = value ;
    return true ;
}

bool hash_table::find(size_t code , size_t& value) const
{
    value = 0 ;

    if(nodes_ == NULL)
        return false ;

    size_t hash = code % size_ ;
    if(nodes_[hash].code != code)
        return false ;

    value = nodes_[hash].value ;
    return true ;
}

void hash_table::clear()
{
    if(nodes_ == NULL)
        return ;

    memset(nodes_ , 0 , sizeof(node) * size_) ;
    count_ = 0 ;
}

size_t hash_table::murmur_hash_value(const char * key , size_t length) 
{
 /*
    'm' and 'r' are mixing constants generated offline.  They're not
    really 'magic', they just happen to work well.
  */

  const unsigned int m= 0x5bd1e995;
  const size_t seed= (0xdeadbeef * length);
  const int r= 24;


  // Initialize the hash to a 'random' value

  size_t h= seed ^ length;

  // Mix 4 bytes at a time into the hash

  const unsigned char * data= (const unsigned char *)key;

  while(length >= 4)
  {
    unsigned int k = *(unsigned int *)data;

    k *= m;
    k ^= k >> r;
    k *= m;

    h *= m;
    h ^= k;

    data += 4;
    length -= 4;
  }

  // Handle the last few bytes of the input array

  switch(length)
  {
  case 3: h ^= ((size_t)data[2]) << 16;
  case 2: h ^= ((size_t)data[1]) << 8;
  case 1: h ^= data[0];
          h *= m;
  default: break;
  };

  /*
    Do a few final mixes of the hash to ensure the last few bytes are
    well-incorporated.
  */

  h ^= h >> 13;
  h *= m;
  h ^= h >> 15;

  return h;
}


size_t hash_table::apr_hash_value(const char * str , size_t size) 
{
    size_t hash = 0 ;
    const unsigned char * key = (const unsigned char *)str ;
    for(size_t idx = 0 ; idx < size ; ++idx , ++key)
    {
        hash = (hash << 5) + hash + *key ;
    }

    return hash ;
}

size_t hash_table::hash_value(const char * str , size_t size) 
{
    //return 0 ;
    return murmur_hash_value(str , size) ;
}

size_t hash_table::next_size()
{
    //size按2的倍数增加,15 --> 31 --> 63
    if(size_ == 0)
    {
        size_ = 31 ;
    }
    else
    {
        size_ = ((size_ + 1) << 2) - 1 ;
    }

    return size_ ;
}

/*
size_t hash_table::hash_value(const char * str , size_t size) 
{
    size_t seed = 0;

    for(size_t idx = 0 ; idx < size ; ++idx)
    {
        seed ^= (size_t)str[idx] + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }

    return seed;
}

//boost的哈希太搓了，取模后冲突率很高。
size_t hash_table::get_prime(int idx)
{
    static size_t primes[ ] = {
    (5ul) , (11ul) , (17ul) , (29ul), (37ul) , (53ul) , (67ul) , (79ul) ,
    (97ul) , (131ul) , (193ul) , (257ul) , (389ul) , (521ul) , (769ul) ,
    (1031ul) , (1543ul) , (2053ul) , (3079ul) , (6151ul) , (12289ul) , (24593ul) ,
    (49157ul) , (98317ul) , (196613ul) , (393241ul) , (786433ul) ,
    (1572869ul) , (3145739ul) , (6291469ul) , (12582917ul) , (25165843ul) ,
    (50331653ul) , (100663319ul) , (201326611ul) , (402653189ul) , (805306457ul) ,
    (1610612741ul) , (3221225473ul) , (4294967291ul)
    } ;

    if(idx < 0 || idx >= 40)
        return 0 ;

    return primes[idx] ;
}
*/

}
}

